The purpose of this research study is to determine whether BCG, a germ found in tuberculosis, in combination with melanoma vaccine (C-VAX) is more effective than BCG and a placebo in 1) stimulation of immune response against melanoma, 2) improving overall survival, and 3) causing a delay in recurrence following surgery. This research is being done because there is no currently approved treatment for melanoma, which prolongs survival time, and no treatment of melanoma, which prolongs the time to recurrence, that does not have significant side effects. It is hoped that the combination of BCG and C-VAX, an experimental test drug will have benefits, which will help solve this problem.